#include <utility>

 struct ListNode {
	int val;
 	struct ListNode *next;
 	ListNode(int x) : val(x), next(nullptr) {}
 };


class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode *addInList(ListNode *head1, ListNode *head2)
    {
        // write code here
        // 边界条件
        if (head1 == nullptr)
            return head2;
        if (head2 == nullptr)
            return head1;
        // 反转两个链表
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        ListNode *dummy = new ListNode(0);
        ListNode *curr = dummy;

        // 存储相加后的本位和进位
        std::pair<int, int> mypair = std::make_pair(0, 0);
        // 进位
        int carry = 0;
        while (head1 || head2 || carry!=0)
        {
            int val1 = head1?head1->val:0;
            int val2 = head2?head2->val:0;
            
            mypair = add(val1, val2, carry);
            ListNode *node = new ListNode(mypair.second);
            // 插入节点-头插法
            node->next = curr->next;
            curr->next = node;
            // 更新进位carry
            carry = mypair.first;
            // 更新指针
            if(head1) head1 = head1->next;
            if(head2) head2 = head2->next;
        }
        return dummy->next;
    }
    // 定义链表反转函数
    ListNode *reverseList(ListNode *head)
    {
        // 边界条件
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *ans = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return ans;
    }
    // 定义节点相加函数
    inline std::pair<int, int> add(int val1, int val2,int carry = 0)
    {
        int sum = val1 + val2 + carry;
        return std::make_pair(sum / 10, sum % 10);
    }
};